package code301_400.code40_50;

import java.util.*;

/**
 * 给定两个数组，编写一个函数来计算它们的交集。
 *
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]
 *
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[9,4]
 *
 */
public class _349intersection {

    /**
     * 执行用时：     * 6 ms     * , 在所有 Java 提交中击败了     * 9.94%     * 的用户
     * 内存消耗：     * 38.4 MB     * , 在所有 Java 提交中击败了     * 79.32%     * 的用户
     *
     * 两个数组都进行排序
     * 执行用时：     * 3 ms     * , 在所有 Java 提交中击败了     * 38.68%     * 的用户
     * 内存消耗：     * 38.6 MB     * , 在所有 Java 提交中击败了     * 39.94%     * 的用户
     * @param nums1
     * @param nums2
     * @return
     */
    public static int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int nowInt;
        int left;
        int right;
        int mid;
        int pre = nums1[0];

        for (int i = 0; i < nums1.length; i++) {
            nowInt = nums1[i];
            if(nums1[i]==pre&&i!=0){
                continue;
            }
            //二分查找
            left = 0;
            right = nums2.length-1;
            while (left<right){
                mid = left + (right - left)/2;
                if(nums2[mid] == nowInt){
                    set.add(nowInt);
                    break;
                }else if(nums2[mid]<nowInt){
                    left = mid + 1;
                }else {
                    right = mid - 1;
                }
            }
            if(nums2[left]==nowInt)set.add(nowInt);
            pre = nums1[i];
        }
        int[] result = new int[set.size()];
        int index = 0;
        for (Integer num : set){
            result[index++] = num;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {1,2,2,1};
        int[] nums2 = {2,2};
        intersection(nums1,nums2);
    }

    /**
     * 题解算法 ： 排序+双指针
     * 如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集
     *
     * 首先对两个数组进行排序，然后使用两个指针遍历两个数组，可以预见的是加入答案的数组元素一定是递增的，为了保证加入元素的一致性。
     * 我们需要额外记录变量pre表示上一次加入答案数组的元素。
     *
     * 初始时，两个指针分别指向两个数组的头部，每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，
     * 如果两个数字相等，且该数字不等于pre，将该数字添加到答案并更新pre变量，同时将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
     *
     * 执行用时：     * 1 ms     * , 在所有 Java 提交中击败了     * 99.84%     * 的用户
     * 内存消耗：     * 38.8 MB     * , 在所有 Java 提交中击败了     * 7.53%     * 的用户
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length,length2 = nums2.length;
        int[] intersection = new int[length1+length2];
        int index = 0,index1 = 0,index2 = 0;
        while (index1<length1&&index2<length2){
            int num1 = nums1[index1],num2 = nums2[index2];
            if(num1 == num2){
                // 保证加入元素的唯一性
                if(index == 0||num1!=intersection[index-1]){
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            }else if(num1<num2){
                index1++;
            }else {
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection,0,index);
    }

}
